#include <iostream>
#include <cstdio>
using namespace std;
int f[101][101], a[101], b[101];
int main()
{
	freopen("company.in", "r", stdin);
	freopen("company.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i] >> b[i];
	int l = 1, r = 10000;
	int mid;
	while (l <= r)
	{
		mid = (l + r + 1) >> 1;
		for (int i = 0; i <= n; i++)
		{
			for (int j = 1; j <= m; j++) f[i][j] = -1e9;
			f[i][0] = 0;
		}
		for (int i = 1; i <= n; i++)
			for (int j = 0; j <= m; j++)
				for (int k = 0; k <= j; k++)
				{
					if (k * a[i] <= mid)
						f[i][j] = max(f[i][j], f[i - 1][j - k] + (mid - k * a[i]) / b[i]);
				}
		if (f[n][m] < m) l = mid + 1;
		else r = mid - 1;
	}
	cout << l;

